/*************************************************************
*
* cam_frustum.cpp
*
* Frustum culling functions
*************************************************************/
#include <m3d/m3d_stdafx.h>

#include <ap_comm.h>
#include <m3d.h>
#include <camera.h>
#include <ap_dbg_var.h>

DBG_VAR_BOOL(dbd_useFineAABBCulling, "render/use fine aabb culling", true);

/*************************************************************
* SPU shared code
*************************************************************/
/******************************************************************
* camFRUSTUM::CullAABB()
* DESCRIPTION:
*  Checks if AABB lies on the one side of any frustum planes
*  (this test can return false-visible)
* OUT:
*  return true if AABB is not visible
******************************************************************/
bool camFRUSTUM::CullAABB(const float * __RESTRICT pAABB) const
{
   if (isAABBValid && dbd_useFineAABBCulling) {
      return CullAABBFine(pAABB);
   } else {
      return CullAABBDraft(pAABB);
   }
}

/******************************************************************
* camFRUSTUM::CullAABBDraft()
* DESCRIPTION:
*  Checks if AABB lies on the one side of any frustum planes
*  (this test can return false-visible)
* OUT:
*  return true if AABB is not visible
******************************************************************/
bool camFRUSTUM::CullAABBDraft(const float * __RESTRICT pAABB) const
{
   m3dV aab;

   for (int iPlane = 0; iPlane < num_planes; ++iPlane) {
      aab.x = ((planes[iPlane].nearest_vert) & 0x1) ? pAABB[0] : pAABB[3];
      aab.y = ((planes[iPlane].nearest_vert) & 0x2) ? pAABB[1] : pAABB[4];
      aab.z = ((planes[iPlane].nearest_vert) & 0x4) ? pAABB[2] : pAABB[5];

      float dist1 = m3dDotProduct(&planes[iPlane].normal, &aab);

      if (dist1 < planes[iPlane].dist) {
         return true;
      }
   }

   return false;
}

/******************************************************************
* camFRUSTUM::CullFrustum()
*
* return true if frustum is not visible
* Attention: don't use for merged frustums
******************************************************************/
bool camFRUSTUM::CullFrustum(const camFRUSTUM & frustum) const
{
   // for each plane
   for (int iPlane = 0; iPlane < num_planes; ++iPlane) {
      int iPoint;
      for (iPoint = 0; iPoint < 8; ++iPoint) {
         float fDot = m3dDotProduct(&planes[iPlane].normal, &frustum.points[iPoint]);
         if (planes[iPlane].dist < fDot) {
            break;
         }
      }
      if (iPoint == 8) {
         return true;
      }
   }
   if (isAABBValid && frustum.isAABBValid && dbd_useFineAABBCulling) {
      if (!aabb.IsIsectBox(&frustum.aabb)) {
         return true;
      }
   }
   return false;
}
/******************************************************************
* camFRUSTUM::CullSphere()
*
* return true if sphere is not visible
******************************************************************/
bool camFRUSTUM::CullSphere(const m3dV & point, float radius) const
{
   // for each frustum plane cull sphere
   for (int iPlane = 0; iPlane < num_planes; ++iPlane) {
      float fDot = planes[iPlane].dist - m3dDotProduct(&planes[iPlane].normal, &point);
      if (fDot > radius) {
         return true;
      }
   }
   if (isAABBValid && dbd_useFineAABBCulling) {
      if (aabb.GetDistToPointSq(point) > m3dPow2(radius)) {
         return true;
      }
   }
   return false;
}
/******************************************************************
* camFRUSTUM::CullSphereHalve()
*
* return true if sphere is not visible
******************************************************************/
bool camFRUSTUM::CullSphereHalve(const m3dV & point, float radius, const camFRUSTUM_PLANE &plane) const
{
   int iPoint, iPlane;

   // for each frustum plane cull sphere
   for (iPlane = 0; iPlane < num_planes; ++iPlane) {
      float fDot = planes[iPlane].dist - m3dDotProduct(&planes[iPlane].normal, &point);
      if (fDot > radius) {
         return true;
      }
   }
   // for halfsphere plane cull frustum points
   for (iPoint = 0; iPoint < 8; ++iPoint) {
      float fDot = m3dDotProduct(&plane.normal, &points[iPoint]);
      if (plane.dist < fDot) {
         break;
      }
   }
   if (iPoint == 8) {
      return true;
   }
   if (isAABBValid && dbd_useFineAABBCulling) {
      if (aabb.GetDistToPointSq(point) > m3dPow2(radius)) {
         return true;
      }
   }
   return false;
}


/******************************************************************
* return true if all points outside frustum
******************************************************************/
bool camFRUSTUM::CullPoints(const m3dV* points, int nPoints) const
{
   // for each plane
   for (int iPlane = 0; iPlane < num_planes; ++iPlane) {
      int iPoint = 0;
      for (; iPoint < nPoints; ++iPoint) {
         float fDot = m3dDotProduct(&planes[iPlane].normal, &points[iPoint]);
         if (planes[iPlane].dist <= fDot) {
            break;
         }
      }
      if (iPoint == nPoints) {
         return true;
      }
   }
   return false;
}



/******************************************************************
* Counstruct plane from three points
******************************************************************/
void camFRUSTUM_PLANE::Construct(const m3dV & p0, const m3dV & p1, const m3dV & p2)
{
   m3dV t1 = p0 - p1;
   m3dV t2 = p2 - p1;

   m3dNormalize(&t1);
   m3dNormalize(&t2);
   m3dCrossProduct(&t1, &t2, &normal);
   m3dNormalize(&normal);
   dist = m3dDotProduct(&normal, &p0);
   
   // calc nearest vert
   nearest_vert = 0;
   for (int i = 0; i < 3; i++) {
      if (normal[i] < 0) {
         nearest_vert |= 1<<i;
      }
   }
}
/******************************************************************
* Counstruct plane from normal and point
******************************************************************/
void camFRUSTUM_PLANE::Construct(const m3dV & _normal, const m3dV & _point)
{
   normal = _normal;
   dist = m3dDotProduct(&normal, &_point);
   
   // calc nearest vert
   nearest_vert = 0;
   for (int i = 0; i < 3; i++) {
      if (normal[i] < 0) {
         nearest_vert |= 1<<i;
      }
   }
}

void camFRUSTUM::SetPlane(int PlaneNum, const camFRUSTUM_PLANE& plane)
{
   planes[PlaneNum]=plane;
}

void camFRUSTUM::ConstructPlane(int PlaneNum, const m3dV & p0, const m3dV & p1, const m3dV & p2)
{
   camFRUSTUM_PLANE plane;
   plane.Construct(p0, p1, p2);

   SetPlane(PlaneNum, plane);
}


void camFRUSTUM::ConstructPlane(int PlaneNum, const m3dV & normal, const m3dV & point)
{
   camFRUSTUM_PLANE plane;
   plane.Construct(normal, point);

   SetPlane(PlaneNum, plane);
}


/*****************************************************
* void camFRUSTUM::UpdatePoints ()
* DESCRIPTION:
* IN:
* OUT:
*****************************************************/
void camFRUSTUM::UpdatePoints( const m3dV _points[8] )
{
   memcpy(points, _points, sizeof(points));
   aabb.Calc(points, 8, 0.0f);
   isAABBValid = true;
}


/*************************************************************
* End of SPU shared code
*************************************************************/

#ifndef SPU

/*****************************************************
* vList - obb points
* Incorrect result if camOrg in obb !!!
*****************************************************/
float GetNearestDistFrustToOBB(const m3dV vList[8], const m3dV & camOrg, const camFRUSTUM_PLANE *pFrustPlanes, const camFRUSTUM_PLANE & nearPlane)
{
   static const int idx[6][4] = {
      {0, 1, 2, 3},
      {7, 6, 5, 4},
      {0, 4, 5, 1},
      {1, 5, 6, 2},
      {2, 6, 7, 3},
      {0, 3, 7, 4},
   };

   float fMinDist = 1e38f;

   m3dPOLY  poly0;
   m3dPOLY  poly1;

   for (int i = 0; i < 6; ++i) {
      poly0.nVert = 4;
      for (int n = 0; n < 4; ++n) {
         poly0.vert[n] = vList[ idx[i][n] ];
      }

      m3dPOLY* pPoly0 = &poly0;
      m3dPOLY* pPoly1 = &poly1;

      int iPlane = 0;
      for (; iPlane < 4; ++iPlane) {
         int ret = m3dClipPolyPlane(pPoly0, &camOrg, &pFrustPlanes[iPlane].normal, pPoly1);
         if (ret == M3D_OUTSIDE) {
            break;
         }
         dsSwap(pPoly0, pPoly1);
      }

      if (iPlane == 4) {
         float fMinDot = 1e38f;
         for (int iVert = 0; iVert < pPoly0->nVert; ++iVert) {
            float fDot = m3dDotProduct(&nearPlane.normal, &pPoly0->vert[iVert]);
            fMinDot = min(fDot, fMinDot);
         }

         fMinDist = min(fMinDist, fMinDot - nearPlane.dist);
      }
   }

   return fMinDist;
}

float camFRUSTUM_PLANE::GetNearestDistToAABB(const m3dBOX & bbox)
{
   m3dV aab;
   aab.x = (nearest_vert & 0x1) ? bbox.fur.x : bbox.bll.x;
   aab.y = (nearest_vert & 0x2) ? bbox.fur.y : bbox.bll.y;
   aab.z = (nearest_vert & 0x4) ? bbox.fur.z : bbox.bll.z;

   return m3dDotProduct(&normal, &aab) - dist;
}

float camFRUSTUM_PLANE::GetNearestDistToOBB(const m3dOBB & obb)
{
   m3dV   vList[8];
   obb.GetVertices(vList);

   float fMinDot = 1e38f;
   for (int i = 0; i < 8; ++i) {
      float fDot = m3dDotProduct(&normal, &vList[i]);
      fMinDot = min(fDot, fMinDot);
   }

   return fMinDot - dist;
}

/*****************************************************
* void camFRUSTUM::ConsturctPointsFromViewProj ()
* DESCRIPTION:
* IN:
* OUT:
*****************************************************/
void camFRUSTUM::ConsturctPointsFromViewProj( const m3dMATR & matrViewProj )
{
#ifdef VID_USE_INVERTED_Z
   static const m3dV UnitPoints[8] = {
      { -1.0f, -1.0f, 1.0f, },   //0
      { -1.0f,  1.0f, 1.0f, },   //1
      { 1.0f,  1.0f, 1.0f, },    //2
      { 1.0f, -1.0f, 1.0f, },    //3
      { -1.0f, -1.0f, 0.0f, },   //4
      { -1.0f,  1.0f, 0.0f, },   //5
      { 1.0f,  1.0f, 0.0f, },    //6
      { 1.0f, -1.0f, 0.0f },     //7
   };
#else
   static const m3dV UnitPoints[8] = {
      { -1.0f, -1.0f, 0.0f, },   //0
      { -1.0f,  1.0f, 0.0f, },   //1
      { 1.0f,  1.0f, 0.0f, },    //2
      { 1.0f, -1.0f, 0.0f, },    //3
      { -1.0f, -1.0f, 1.0f, },   //4
      { -1.0f,  1.0f, 1.0f, },   //5
      { 1.0f,  1.0f, 1.0f, },    //6
      { 1.0f, -1.0f, 1.0f },     //7
   };
#endif

   // Get invert matrix
   m3dMATR matrInv;
   if (matrViewProj.Invert(&matrInv) == FALSE) {
      ASSERT(0);
      num_planes = 0;
      return;
   }

   // Calc corner points in world space
   for (int i = 0; i < 8; ++i) {
      m4dV  vTmp;
      matrInv.TransformPoint(&UnitPoints[i], &vTmp);

      // perspective division
      points[i].x = vTmp.x / vTmp.w;
      points[i].y = vTmp.y / vTmp.w;
      points[i].z = vTmp.z / vTmp.w;
   }
}

/******************************************************************
* camFRUSTUM::ConstructFromViewProj()
*
* Construct six cull-planes for ViewProj matrix
******************************************************************/
void camFRUSTUM::ConstructFromViewProj(const m3dMATR & matrViewProj)
{
   ConsturctPointsFromViewProj(matrViewProj);

   // set the planes in most-likely-to-reject order
/*
   ConstructPlane(0, points[0], points[1], points[2]); // near
   ConstructPlane(1, points[0], points[4], points[5]); // left
   ConstructPlane(2, points[2], points[6], points[7]); // right
   ConstructPlane(3, points[6], points[5], points[4]); // far
   ConstructPlane(4, points[3], points[7], points[4]); // lower
   ConstructPlane(5, points[1], points[5], points[6]); // upper
*/

   ConstructPlane(0, points[0], points[4], points[5]); // left
   ConstructPlane(1, points[2], points[6], points[7]); // right
   ConstructPlane(2, points[3], points[7], points[4]); // lower
   ConstructPlane(3, points[1], points[5], points[6]); // upper
   ConstructPlane(4, points[0], points[1], points[2]); // near
   ConstructPlane(5, points[6], points[5], points[4]); // far


   num_planes = 6;
   return;
}


char planes_idx[6][4] = {
   {0, 4, 5, 1},
   {2, 6, 7, 3},
   {3, 7, 4, 0},
   {1, 5, 6, 2},
   {0, 1, 2, 3},
   {6, 5, 4, 7},
};

char planes_edge[6][4] = {
   {2, 5, 3, 4},
   {3, 5, 2, 4},
   {1, 5, 0, 4},
   {0, 5, 1, 4},
   {0, 3, 1, 2},
   {3, 0, 2, 1},
};

/******************************************************************
*
******************************************************************/
void camFRUSTUM::ConstructForParallelLight(const m3dMATR & matrCamViewProj, const m3dV & light_dir)
{
   bool  used[6];

   camFRUSTUM cam_frustum;
   cam_frustum.ConstructFromViewProj(matrCamViewProj);

   num_planes = 0;
   for (int iCamPlane = 0; iCamPlane < cam_frustum.num_planes; ++iCamPlane) {
      const camFRUSTUM_PLANE* pCamPlane = &cam_frustum.planes[iCamPlane];
      if (m3dDotProduct(&pCamPlane->normal, &light_dir) <= 0.0f) {
         SetPlane(num_planes, *pCamPlane);
         num_planes++;
         used[iCamPlane] = true;
      } else {
         used[iCamPlane] = false;
      }
   }

   int   i;
   for (i = 0; i < 6; ++i) {
      if (used[i]) {
         for (int iEdge = 0; iEdge < 4; ++iEdge) {
            if (!used[ planes_edge[i][iEdge] ]) {
               // add new plane
               int   idx0 = planes_idx[i][iEdge];
               int   idx1 = planes_idx[i][(iEdge + 1) % 4];
               m3dV  vec = cam_frustum.points[idx1] + light_dir * 10.0f;
               ConstructPlane(num_planes, cam_frustum.points[idx0], cam_frustum.points[idx1], vec);
               num_planes++;
            }
         }
      }
   }
   return;
}

/******************************************************************
* camFRUSTUM::AddFrustum()
*
* Merge frustums (for shadow)
******************************************************************/
void camFRUSTUM::AddFrustum(const camFRUSTUM & cam_frustum, const m3dV & light_origin)
{
   for (int iCamPlane = 0; iCamPlane < cam_frustum.num_planes; ++iCamPlane) {
      const camFRUSTUM_PLANE* pCamPlane = &cam_frustum.planes[iCamPlane];
      if (pCamPlane->dist < m3dDotProduct(&pCamPlane->normal, &light_origin)) {
         //if (num_planes >= MAX_CAM_FRUSTUM_PLANES) {
         //   break;
         //}
         STRONG_ASSERT(num_planes < MAX_CAM_FRUSTUM_PLANES);
         SetPlane(num_planes, *pCamPlane);
         num_planes++;
      }
   }
   return;
}



/******************************************************************
* camFRUSTUM::CullPoint()
*
* return true if point is not visible
******************************************************************/
bool camFRUSTUM::CullPoint(const m3dV & point) const
{
   // for each plane
   for (int iPlane = 0; iPlane < num_planes; ++iPlane) {
      float fDot = m3dDotProduct(&planes[iPlane].normal, &point);
      if (planes[iPlane].dist > fDot) {
         return true;
      }
   }
   return false;
}


/******************************************************************
* camFRUSTUM::CullTriangle()
*
* return true if triangle is not visible
******************************************************************/
bool camFRUSTUM::CullTriangle(const m3dV & v0, const m3dV & v1, const m3dV & v2) const
{
   float fDot;
   // for each plane
   for (int iPlane = 0; iPlane < num_planes; ++iPlane) {
      fDot = m3dDotProduct(&planes[iPlane].normal, &v0);
      if (planes[iPlane].dist <= fDot) {
         continue;
      }
      fDot = m3dDotProduct(&planes[iPlane].normal, &v1);
      if (planes[iPlane].dist <= fDot) {
         continue;
      }
      fDot = m3dDotProduct(&planes[iPlane].normal, &v2);
      if (planes[iPlane].dist <= fDot) {
         continue;
      }
      return true;
   }
   return false;
}


/******************************************************************
* camFRUSTUM::CullCapsule()
*
* return true if capsule is not visible
******************************************************************/
bool camFRUSTUM::CullCapsule(const m3dV & point1, const m3dV & point2, float radius) const
{
   // for each plane
   for (int iPlane = 0; iPlane < num_planes; ++iPlane) {
      float fDot1 = planes[iPlane].dist - m3dDotProduct(&planes[iPlane].normal, &point1);
      float fDot2 = planes[iPlane].dist - m3dDotProduct(&planes[iPlane].normal, &point2);
      if (fDot1 > radius && fDot2 > radius) {
         return true;
      }
   }
   return false;
}

#endif // _SPU
//
// End-of-file cam_frustum.cpp
//
